package leecode

func hasPathSum(root *TreeNode, targetSum int) bool {
	if root == nil {
		return false
	}
	var pathSum func(node *TreeNode, count int) bool
	pathSum = func(node *TreeNode, count int) bool {
		//终止条件 遇到叶子节点且找到目标值
		if node.Left == nil && node.Right == nil && count == 0 {
			return true
		}
		if node.Left == nil && node.Right == nil {
			//没有找到目标值
			return false
		}
		//左
		if node.Left != nil {
			count -= node.Left.Val
			if pathSum(node.Left, count) {
				return true
			}
			count += node.Left.Val //回溯
		}
		//右
		if node.Right != nil {
			count -= node.Right.Val
			if pathSum(node.Right, count) {
				return true
			}
			count += node.Right.Val //回溯
		}
		return false
	}
	return pathSum(root, targetSum-root.Val)
}
